#include <stdio.h>

// 递归法实现
int binary_search(int arr[], int start, int end, int target)99
{
    if (start > end) {  // 基本结束条件
        return -1;
    }

    int mid = start + (end - start) / 2;  // 计算中间元素的索引

    if (target == arr[mid]) {  // 如果目标值就是中间元素，返回中间元素的索引
        return mid;
    }
    else if (target < arr[mid]) {  // 目标值在左半部分，继续递归查找左半部分
        return binary_search(arr, start, mid - 1, target);
    }
    else {  // 目标值在右半部分，继续递归查找右半部分
        return binary_search(arr, mid + 1, end, target);
    }
}

int main()
{
    int arr[] = {1, 3, 5, 7, 11, 14, 17, 22, 25, 44};
    int n = sizeof(arr) / sizeof(int); // 数组元素个数
    int target = 7;  // 目标值
    int result = binary_search(arr, 0, n - 1, target);

    if (result == -1) {
        printf("未找到目标值 %d\n", target);
    }
    else {
        printf("目标值 %d 在数组第 %d 处\n", target, result+1);
    }
    return 0;
}